package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;

import util.LogUtils;

/*
 * 
原题
	Given a linked list, determine if it has a cycle in it.
	
	Follow up:
	Can you solve it without using extra space?
题目大意	
	给定一个单链表，判断链表是否有环。 
解题思路
　　设置两个指针(fast, slow)，初始值都指向头，
	slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，
		两个指针必定相遇 
		
 * @Date 2017-09-14 11：48
 */
public class _141_Linked_List_Cycle {
	public static class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}
	
	public boolean hasCycle(ListNode head) {
		ListNode pFast = head, pSlow = head;
	
		while (pFast!=null && pFast.next!=null) {		//加入pFast先行到链表尾,那就证明链表肯定没有环了
			pFast = pFast.next.next;		//一次遍历两个节点
			pSlow = pSlow.next;
			if (pFast == pSlow)	return true;
		}
		return false;
	}

	private ListNode newLinkList2() {
		ListNode root = new ListNode(1);
		ListNode loopStart = null;
		root.next = new ListNode(2);
		root.next.next = new ListNode(3);
		root.next.next.next = new ListNode(4);
		root.next.next.next.next = new ListNode(5);
		loopStart = root.next.next.next.next;					//环起点
		root.next.next.next.next.next = new ListNode(6);
		root.next.next.next.next.next.next = new ListNode(7);
		root.next.next.next.next.next.next = new ListNode(8);
		root.next.next.next.next.next.next.next = new ListNode(9);
		root.next.next.next.next.next.next.next.next = new ListNode(10);
		root.next.next.next.next.next.next.next.next.next = new ListNode(11);
		root.next.next.next.next.next.next.next.next.next.next = new ListNode(12);
		root.next.next.next.next.next.next.next.next.next.next.next = new ListNode(13);
		root.next.next.next.next.next.next.next.next.next.next.next.next = new ListNode(14);
		root.next.next.next.next.next.next.next.next.next.next.next.next.next = loopStart;
		return root;
	}
	
	public static void main(String[] args) {
		_141_Linked_List_Cycle obj = new _141_Linked_List_Cycle();
		LogUtils.println("结果", 
				obj.hasCycle(
//						obj.newLinkList2()
						new ListNode(1)
				));
	}

}
